// https://leetcode.cn/problems/minimum-window-substring/submissions/

class Solution {
public:
    string minWindow(string s, string t) {
        map<char, int> rec;
        int j = 0;
        int cnt = 0;
        int minLen = INT_MAX;
        int start = 0;
        for (int i = 0; i < t.length(); ++i) {
            rec[t[i]]++;
        }
        for (int i = 0; i < s.length(); ++i) {
            rec[s[i]]--;
            if (rec[s[i]] >= 0) {
                cnt++;
                while (cnt == t.length()) {
                    if (i - j + 1 < minLen) {
                        minLen = i - j + 1;
                        start = j;
                    }
                    rec[s[j]]++;
                    if (rec[s[j]] > 0) {
                        cnt--;
                    }
                    ++j;
                }
            }
        }
        if (minLen == INT_MAX) return "";
        return s.substr(start, minLen);
    }
};